class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int n = coins.size();
            vector<vector<int>> dp(n+1,vector<int>(amount+1));
            for(int i =1 ; i < amount+1 ; i++) dp[0][i] = 0x3f3f3f3f;
            for(int i = 1 ; i < n+1 ; i++){
                for(int j= 1 ; j < amount+1 ; j++){
                    dp[i][j] = j>=coins[i-1] ? min(dp[i-1][j],dp[i][j-coins[i-1]]+1):dp[i-1][j];
                }
            }
            return dp[n][amount] == 0x3f3f3f3f ? -1 : dp[n][amount];
        }
    };